class Solution {
    public:
        int maxSum(vector<int>& nums) {
            unordered_set<int> window;
            int ans = 0, m = -1000;
            for (auto i : nums) {
                m = max(m, i);
                if (i > 0 && (window.count(i) == 0) ) {
                    ans += i;
                    window.insert(i);
                }
            }
            if (ans == 0)
                return m;
            else
                return ans;
        }
    };

    class Solution {
        public:
            vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
                int n = nums.size(), m = queries.size();
                vector<int> ans(n, INT_MAX);
                unordered_map<int, pair<int, int>> window;
                for (int i = 0; i < n; i++) {
                    if (window.find(nums[i]) == window.end()){
                        window[nums[i]].first = window[nums[i]].second = i;
                        ans[i] = INT_MAX;
                    }
                    else {
                        ans[i] = min(i - window[nums[i]].second,
                                     window[nums[i]].first + n - i);
                        ans[window[nums[i]].first] = min(ans[window[nums[i]].first],
                                                         window[nums[i]].first + n - i);
                        ans[window[nums[i]].first] =
                            min(ans[window[nums[i]].first],
                                i - window[nums[i]].first);
                        
                        ans[window[nums[i]].second] = min(
                            ans[window[nums[i]].second],i - window[nums[i]].second);
                        window[nums[i]].second = i;
                    }
                }
                // for (int i = 0; i < n; i++) {
                //     cout << ans[i] << ' ';
                // }
                vector<int> ans2(m, -1);
                for (int i = 0; i < m; i++) {
                    ans2[i] = ans[queries[i]];
                    if (ans2[i] == INT_MAX) {
                        ans2[i] = -1;
                    }
                }
                return ans2;
            }
        };
        bool fun(int mode, unordered_map<int, int>& cnt) {
            vector<bool> m(mode + 1);
            m[0] = true;
            for (auto& e : cnt) {
                int a = e.first, b = e.second;
                while (b--) {
                    for (int i = mode; i >= a; i--) {
                        if (m[i - a]) 
                            m[i] = true;
                    }
                }
            }
            return m[mode];
        }
        class Solution {
        public:
            int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
                int n = nums.size(), m = queries.size();
                vector<unordered_map<int, int>> add(n + 1);
                vector<unordered_map<int, int>> sub(n + 1);
                unordered_map<int, int> cnt;
                int pos = 0, k = 0;
                while (pos < n) {
                    // cnt += tmp[pos];
                    for (auto& e : add[pos]) {
                        cnt[e.first] += e.second;
                    }
                    for (auto& e : sub[pos]) {
                        cnt[e.first] -= e.second;
                        if (cnt[e.first] == 0) {
                            cnt.erase(e.first);
                        }
                    }
                    while (!fun(nums[pos],cnt)) {
                        if (k == m)
                            return -1;
                        int l = queries[k][0], r = queries[k][1], val = queries[k][2];
                        if (l <= pos && r >= pos)
                            cnt[val]++;
                        // tmp[l] += val, tmp[r + 1] -= val, k++;
                        add[l][val]++, sub[r + 1][val]++,k++;
                        // cout << pos << ' '  << ' ' << k << endl;
                    }
                    pos++;
                }
                return k;
            }
        };